// tspcluster - Traveling Salesman Problem
// Copyright (C) 2006  Frederik Carlier
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

using System;
using System.Collections.Generic;
using System.Text;

namespace UGent.Tsp
{
    public class Route : IRoute
    {
        private static Random random = new Random();
        #region Constructors
        public Route()
            : this(2, 100, Metric.Euclidian)
        {
        }

        public Route(int dimension, int cityCount, Metric metric)
            : this(new Map(dimension, cityCount, metric, true))
        {
        }

        public Route(Map map)
        {
            if (map == null)
                throw new ArgumentNullException("map");

            this.map = map;
            this.cityCount = map.CityCount;

            // Initialize a random route;
            RandomPermutation permutations = new RandomPermutation(random);
            this.route = permutations.Next(cityCount);
        }
        #endregion

        #region Properties
        private int[] route;
        private int cityCount;

        private Map map;
        public Map Map
        {
            get { return map; }
        }

        public int this[int i]
        {
            get
            {
                if (i >= 0 && i < cityCount)
                    return route[i];
                else
                    return route[Cyclic.GetIndex(i, cityCount)];
            }
            set
            {
                if (i >= 0 && i < cityCount)
                    route[i] = value;
                else
                    route[Cyclic.GetIndex(i, cityCount)] = value;
            }
        }

        /// <summary>
        /// Returns <see langword="true"/> if the route is a valid route;
        /// <see langword="false"/> otherwise.
        /// </summary>
        public bool IsValid
        {
            get
            {
                int[] count = new int[cityCount];

                for (int i = 0; i < cityCount; i++)
                {
                    if (route[i] < 0 || route[i] >= cityCount)
                        return false;

                    count[route[i]] += 1;
                }

                for (int i = 0; i < cityCount; i++)
                {
                    if (count[i] != 1)
                        return false;
                }

                return true;
            }
        }
        #endregion

        #region Methods
        public double GetLength()
        {
            double length = 0;

            for (int i = 0; i < cityCount; i++)
            {
                length += GetDistance(i, i + 1);
            }

            return length;
        }

        public double GetLength(int[] route)
        {
            double length = 0;

            for (int i = 0; i < route.Length - 1; i++)
            {
                length += Map.GetDistance(Cyclic.GetIndex(route[i], cityCount), Cyclic.GetIndex(route[i + 1], cityCount));
            }

            length += Map.GetDistance(Cyclic.GetIndex(route[route.Length - 1], cityCount), Cyclic.GetIndex(route[0], cityCount));
            return length;
        }

        public double GetDistance(int i, int j)
        {
            int i1 = this[i];
            int i2 = this[j];
            return Map.GetDistance(i1, i2);
        }

        /// <summary>
        /// Swaps the two cities at position <paramref name="i"/> and
        /// <paramref name="j"/>
        /// </summary>
        /// <param name="i">The first position.</param>
        /// <param name="j">The second position.</param>
        public void Swap(int i, int j)
        {
            int temp = this[i];
            this[i] = this[j];
            this[j] = temp;
        }

        /// <summary>
        /// Does a cyclic permutation of the cities between <paramref name="first"/>
        /// and <paramref name="last"/>.
        /// </summary>
        /// <param name="first">The first city to permute.</param>
        /// <param name="last">The last city to permute.</param>
        public void PermutateCyclic(int first, int last)
        {
            int temp = this[first];

            for (int i = first; i < last; i++)
                this[i] = this[i + 1];

            this[last] = temp;
        }
        
        internal int[] GetRoute()
        {
            return route;
        }
        #endregion
    }
}
